class Solution(object):
    def findSmallestRegion(self, regions, region1, region2):
        """
        :type regions: List[List[str]]
        :type region1: str
        :type region2: str
        :rtype: str
        """
        d = {}
        edges = {}
        for item in regions:
            d[item[0]] = 0
            for j in range(1, len(item)):
                edges[item[j]] = item[0]
                d[item[j]] = 0
        region = region1
        while region in edges:
            if d[region] == 1:
                return region
            else:
                d[region] = 1
                region = edges[region]
        d[region] = 1
        region = region2
        while region in edges:
            if d[region] == 1:
                return region
            else:
                d[region] = 1
                region = edges[region]
        return region




data = Solution()
regions = [["Earth", "North America", "South America"], ["North America", "United States", "Canada"],
           ["United States", "New York", "Boston"], ["Canada", "Ontario", "Quebec"], ["South America", "Brazil"]]
region1 = "New York"
region2 = "Brazil"
print(data.findSmallestRegion(regions, region1, region2))
